package fun.codedesign.jdk.math.fibonacci;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Fibonacci {
    private static Map<Integer, Integer> fibCache = new HashMap<>();

    /**
     * fibnacci数列是指下一个值等于前两个值之和 0,1,1,2,3,5... 实现的方法可以用递归的方式,list的方式，或者map缓存的方式
     * 经FIXME:map的底层是链表和数组可能会存在性能上的效率，containsKey和get数值的时候过比较，采用ArrayList的方式最效率
     * 
     *
     * @throws Exception
     */
    public static void main(String[] args) {
        /* System.out.println(fibonacci(-1)); */// java.lang.IllegalArgumentException:
        // Illegal Capacity: -1
        System.out.println(fibonacci(0));
        System.out.println(fibonacci(1));
        System.out.println(fibonacci(2));
        System.out.println(fibonacci(3));
        System.out.println(fibonacci(4));
        // 超过范围抛出异常
        final long l1 = System.nanoTime();
        System.out.println(fibonacci(47));
        final long l2 = System.nanoTime();
        /* System.out.println(fibonacci(10000)); */
        // 运行时间太长
        System.out.println(fibN(47));
        // 最大到46
        final long l3 = System.nanoTime();
        System.out.println(cachedFibN(47));
        final long l4 = System.nanoTime();
        System.out.println("list方法耗时:" + (l2 - l1) + "纳秒"); // 0.22ms 本方法修改为返回单个数值效率最高，时间0.082ms
        System.out.println("纯递归方法耗时:" + (l3 - l2) + "纳秒"); // 13 s
        System.out.println("map缓存方法耗时:" + (l4 - l3) + "纳秒");  // 0.13ms
    }

    /**
     * 返回整个集合 时间复杂度O(n) 空间复杂度O(1)
     *
     * @param n从1开始
     * @return
     * @throws Exception
     */
    public static int/*List<Integer>*/ fibonacci(int n) {
        // 但传入为0时也需要抛异常
        if (n < 1) {
            throw new IllegalArgumentException("n must not be less than 1");
        }
        // 如果传入的是负数，此处会抛出异常，所以不需要额外写, 以上统一拦截了
        List<Integer> list = new ArrayList<>(n);

        int temp = 0;
        for (int i = 0; i < n; i++) {
            /*int */
            temp = 0;
            if (i == 0) {
                temp = 0;
            } else if (i == 1) {
                temp = 1;
            } else {
                temp = list.get(i - 1) + list.get(i - 2);
                if (temp < 0) {
                    // 相加为负数后，说明超出了Integer的取值范围
                    throw new ValueOutOfRangeException("value must not be greater than " + Integer.MAX_VALUE);
                }
            }
            list.add(temp);
        }
        return /*collection*/ temp;
    }

    /**
     * 递归实现是 时间复杂度O(n*n),两个递归都需要重新计算
     *
     * @param n
     * @return
     */
    public static int fibN(int n) {
        if (n < 1) {
            throw new IllegalArgumentException("n must not be less than 1");
        }
        if (n == 1) {
            return 0;
        }
        if (n == 2) {
            return 1;
        }
        return fibN(n - 1) + fibN(n - 2);
    }

    /**
     * 缓存递归法，时间复杂度O(n)
     *
     * @param n
     * @return
     */
    public static int cachedFibN(int n) {
        if (n < 1) {
            throw new IllegalArgumentException("n must not be less than 1");
        }
        fibCache.put(1, 0);
        fibCache.put(2, 1);
        return recursiveCachedFibN(n);
    }

    /**
     * 利用成员变量 fibCache,不能使用方法中的成员变量
     *
     * @param n
     * @return
     */
    private static int recursiveCachedFibN(int n) {
        // 关键：直接从cache中取值，而不需要再重复计算一次
        if (fibCache.containsKey(n)) {
            return fibCache.get(n);
        }
        // 递归
        int value = recursiveCachedFibN(n - 1) + recursiveCachedFibN(n - 2);
        if (value < 0) {
            // 相加为负数后，说明超出了Integer的取值范围
            throw new ValueOutOfRangeException("value must not be greater than " + Integer.MAX_VALUE);
        }
        fibCache.put(n, value);
        return value;
    }
}
